Modern communication systems use a variety of data processing techniques to ensure that data received at a receiver can be correctly decoded, that is, comprehended. Various forms of error detection and error correction codes have been developed that add redundancy to message symbols that can be used to detect and correct errors in the code word up to a given limit or merely to detect errors up to a larger limit. Bose-Chaudhuri-Hocquenghem (BCH) codes and Reed-Solomon (RS) codes are among the most widely used block codes for communication systems and storage systems. The mathematics underlying BCH and RS codes is explained in, for example, E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968 and, for example, S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, Englewood Cliffs, N-J, 1983, which are incorporated herein by reference for all purposes.
As is well understood within the art an (N, K) BCH or RS code has K message symbols and N coded symbols, where each symbol belongs to GF(q) for a BCH code or GF(qm) for an RS code. A binary (N, K) BCH code can correct up to t errors with N=2m−1, where N−K is greater than or equal to 2t. An (N, K) RS code can correct t errors and p erasures with 2t+ρ≦N−K. For binary BCH codes, an error can be corrected by finding the error locator and error evaluator polynomials. In RS codes, an erasure is defined to be an error with a known error location. The steps performed by most RS decoder architectures for correction of errors can be summarised as follows:    (1) calculate the syndromes for the received code words,    (2) compute the error locator polynomial and the error evaluator polynomial,    (3) find the error locations, and    (4) compute the error values.
If both errors and erasures are corrected, the four steps are modified to be:    (1) calculate the syndromes and Forney syndromes from the received code words and the erasure locations,    (2) compute the errata locator polynomial and the errata evaluator polynomial,    (3) find the errata locations, and    (4) compute the errata value.
In effect, the received data R(x) is provided to a syndrome generator to generate a syndrome polynomial, S(x), which represents the error pattern of the code word from which errors can be corrected. The syndromes depend only on the error pattern, which is part of the syndrome, and not on the transmitted code word. A key equation solver, which uses the well-known Berlekamp-Massey algorithm, is used to generate an error locator polynomial, σ(x), and an error evaluator polynomial, Ω(x). The error locator polynomial, σ(x), provides an indication of the locations of any errors. The error evaluator polynomial provides the values of the located errors. Typically, the error locator polynomial is processed by a Chien search engine to generate the roots, β1−1, of the polynomial, which roots provide the locations of any errors. The values of the errors are calculated using the roots together with the error evaluator polynomial, Ω(x).
As is well understood by those skilled in the art there exists various architectures for solving the key equation. Preferred architectures implement an inverse-free Berlekamp-Massey algorithm. Architectures for implementing the algorithm are typically implemented using a parallel processing architecture, which has the disadvantage of requiring the relatively large area and having a relatively high logic circuit delay but with the advantage of a low processing latency. Alternatively, architectures might use a serial processing architecture, which has the disadvantage of a relatively large processing latency but the advantage of a relatively low area and logic delays. However, in the context of a complete decoding system, the increased decoding latency requires increased data buffer sizes that, in turn, require additional space. It will be appreciated by those skilled in the art that the area of any given processing architecture increases significantly as the number of finite field multipliers increases.
It is an object of embodiments of the present invention at least to mitigate some of the problems of the prior art.